package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;


class TreeInfo {

    // 可以类参数替代
//    private int maxDistance;

    public  int maxDistanceOfTree(TreeNode root) {

        int[] maxDistance = new int[1];
         traversalTree(root,maxDistance);

         return maxDistance[0];
    }

    private int traversalTree(TreeNode node, int[] maxDistance) {

        if (node == null) {

            return 0;
        }

        int leftDistance = traversalTree(node.left,maxDistance);
        int rightDistance = traversalTree(node.right,maxDistance);

        maxDistance[0] = Math.max(maxDistance[0],leftDistance + rightDistance + 1);
        return Math.max(leftDistance,rightDistance) + 1;
    }

}


public class _20_二叉树节点间的最大距离 {

    public static void main(String[] args) {

        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         *                     /
         *                    20
         *                    /
         *                   30
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.left.left = new TreeNode(20);
        t1.right.left.left.left = new TreeNode(30);
        t1.right.right = new TreeNode(10);

        TreeInfo treeInfo = new TreeInfo();

        System.out.println(treeInfo.maxDistanceOfTree(t1));
    }

}
